package 中等.搜索.深度优先搜索;

import util.TreeNode;

/**
 * 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
 * 如果指定节点没有对应的“下一个”节点，则返回null。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/successor-lcci/
 */
public class 后继者_04_06 {

    public static void main(String[] args) {

        TreeNode node2 = new TreeNode(2);
        TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        node2.left = node1;
        node2.right = node3;
        System.out.println(new 后继者_04_06().inorderSuccessor(node2, node1).val);

    }

    /**
     * 递归
     *
     * @param root
     * @param p
     * @return
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {

        TreeNode target = new TreeNode(-1);
        Flag flag = new Flag();
        dfs(root, p, target, flag);

        return target.val == -1 ? null : target;

    }

    public void dfs(TreeNode node, TreeNode p, TreeNode target, Flag flag) {
        if (node == null) {
            return;
        }
        dfs(node.left, p, target, flag);

        if (flag.val && target.val == -1) {
            target.val = node.val;
            return;
        }
        if (node.val == p.val) flag.val = true;

        dfs(node.right, p, target, flag);
    }

    class Flag {

        private boolean val;

    }

    /**
     * BST性质+二分查找
     *
     * @param root
     * @param p
     * @return
     */
    public TreeNode inorderSuccessor2(TreeNode root, TreeNode p) {

        while (root != null) {

            if (root.val == p.val) {
                root = root.right;
                break;
            } else if (root.val > p.val) {
                break;
            } else {
                root = root.right;
            }


        }


        return new TreeNode();
    }

}
